In their landmark papers in 1977 and 1978, Ziv and Lempel proposed two universal lossless data compression algorithms, which are called LZ77 and LZ78, respectively. Since then, many variants were suggested such as the Lempel-Ziv-Welch (LZW), the Lempel-Ziv-Storer-Szymanski (LZSS), and the Lempel-Ziv-Ross (LZR). Among these variants of the original LZ78, the LZW, designed by Welch in 1984, is perhaps the most famous and popular modification. It has been adopted for use in many systems and standards including the UNIX system, the Graphics Interchange Format (GIF) standard, the V.42bis modern standard, and in the TIFF image and PDF formatted documents as an has option.
A straightforward approach to protect the bit stream generated from LZW algorithm is to encrypt it using a stream cipher, that is, applying an exclusive or (XOR) operations on the LZW bit stream and a key stream. However, this scheme is very vulnerable to the chosen-plaintext attack. Specifically, an attacker can encode a source symbol sequence S and obtain the compressed and encrypted bit stream Y. Since the LZW algorithm is publicly known, the attacker can easily determine the intermediate bit stream X produced by the LZW encoder. Therefore, the key stream can be easily recovered by taking K=X⊕Y, where ⊕ is the XOR operator. Alternatively, one can encrypt the bit stream generated from the LZW algorithm using a block cipher such as those defined in the Advanced Encryption Standard (AES). Indeed, this encryption scheme provides very high security features. However, an important disadvantage of the block cipher is that it is complicated and computationally slow, compared with the stream cipher, as the block cipher normally involves several rounds of table lookup operations, XOR operations, and mixing operations. In addition, since in most multimedia applications, the required security level is much lower than that in the military applications, it may not be necessary to use the AES to achieve such a high security at the cost of slow computations.
There are existing systems and methods that exploit the LZW algorithm itself for achieving high security features. For example, Xie et al. “Secure Lempel Ziv Compression with Embedded Encryption,” Proc. SPIE, vol. 5681, pp. 318-327, 2005 describes an encryption scheme based on the LZ78 method. The basic idea is to build multiple dictionaries with different entry orders, and then select a random dictionary in each compression step. These existing methods, however, are still vulnerable to a number of attacks such as the chosen-plaintext attack.